﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using ProjectEuler.Runtime;

namespace ProjectEuler
{
    public sealed class Combination<T> : ICloneable, ICollection<T>, IEnumerable<T>
    {
        private readonly Int32[] _indices;
        private readonly T[] _items;

        public Combination(IEnumerable<T> items, Int32 k)
        {
            Contract.EnsureNotNull("items", items);
            Contract.EnsureNotNegative("k", k);

            _items = items.ToArray();
            _indices = new Int32[k];

            for (var i = 0; i < k; ++i)
            {
                _indices[i] = i;
            }
        }

        private Combination(T[] items, Int32[] indices)
        {
            _items = items;
            _indices = indices;
        }

        public T this[Int32 index]
        {
            get { return _items[_indices[index]]; }
        }

        public Int32 N
        {
            get { return _items.Length; }
        }

        public Int32 K
        {
            get { return _indices.Length; }
        }

        public Combination<T> Clone()
        {
            return new Combination<T>(_items, CloneIndices());
        }

        public void CopyTo(T[] array, Int32 arrayIndex)
        {
            for (int i = 0; i < K; i++)
            {
                array[arrayIndex + i] = this[i];
            }
        }



        public IEnumerator<T> GetEnumerator()
        {
            for (var i = 0; i < K; i++)
            {
                yield return this[i];
            }
        }

        public Combination<T> Next()
        {
            if (_indices[0] == (N - K))
            {
                return null;
            }

            var result = CloneIndices();
            var i = K - 1;

            while ((i > 0) && (result[i] == ((N - K) + i)))
            {
                i--;
            }

            ++result[i];

            for (var j = i; j < K - 1; ++j)
            {
                result[j + 1] = result[j] + 1;
            }

            return new Combination<T>(_items, result);
        }

        public override String ToString()
        {
            var result = new StringBuilder("{ ");

            foreach (var item in this)
            {
                result.Append(item);
                result.Append(' ');
            }

            result.Append('}');
            return result.ToString();
        }

        public Combination<T> Element(Int32 m)
        {
            var result = new Int32[K];

            var a = N;
            var b = K;
            var x = Combinations.Count(N, K) - 1 - m;

            for (var i = 0; i < K; ++i)
            {
                result[i] = LargestV(a, b, x);

                x -= Combinations.Count(result[i], b);
                a = result[i];
                b -= 1;
            }

            for (var i = 0; i < K; ++i)
            {
                result[i] = (N - 1) - result[i];
            }

            return new Combination<T>(_items, result);
        }

        Object ICloneable.Clone()
        {
            return Clone();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private Int32[] CloneIndices()
        {
            return (Int32[])(_indices.Clone());
        }

        private static Int32 LargestV(Int32 a, Int32 b, Double x)
        {
            var v = a - 1;

            while (Combinations.Count(v, b) > x)
            {
                --v;
            }

            return v;
        }

        void ICollection<T>.Add(T item)
        {
            throw new NotSupportedException();
        }

        void ICollection<T>.Clear()
        {
            throw new NotSupportedException();
        }

        Boolean ICollection<T>.Contains(T item)
        {
            foreach (var i in this)
            {
                if (EqualityComparer<T>.Default.Equals(item, i))
                {
                    return true;
                }
            }

            return false;
        }

        Int32 ICollection<T>.Count
        {
            get { return K; }
        }

        Boolean ICollection<T>.IsReadOnly
        {
            get { return true; }
        }

        Boolean ICollection<T>.Remove(T item)
        {
            throw new NotSupportedException();
        }
    }
}